In the design of digital filters of large order N having demanding computational speed, range and other requirements, the use of transform methods, e.g., FFT has a number of drawbacks.
It has been proposed to overcome these shortcomings by use of residue number system (RNS) techniques.
Use of the residue number system in signal processors permits parallel processing using multi-channel, short word length circuit configurations. An RNS signal processor transforms numbers from binary or decimal form into residue form which represents the number by a distinct set of smaller residue values. Once the value is in residue form, the signal processor is able to perform certain arithmetical operations using the so-called system of residue class arithmetic.
Residue class arithmetic is a modulo form of calculation. Here any value must be within a modulus range from zero through the modulus. The system is periodic: any value outside the modulus range is transformed to a corresponding value within the modulus range. This corresponding value is the integer difference between the numeric value and the greatest multiple of the modulus less than the numeric value.
To convert a decimal number N to its modulus value, a division is performed with the decimal number, N, being the divident and the modulus, p.sub.i, or multiples thereof less than N, being the divisor. The remainer, r.sub.i, of this division is the modulus representation called the residue. The relationship is sometimes expressed as: EQU N=r.sub.i mode.sub.i ( 1)
Thus where the modulus, P.sub.i, is 7 and the numeric value, N, is 10 its modulus value or residue, r.sub.i, is 10-7=3. If the numeric value is 16 its residue value is 16-(2.multidot.7)=2.
Residue number systems of interest herein use moduli from a restricted moduli set made up of pairwise relatively prime integers. Relatively prime or mutually prime numbers as used herein refer to moduli which have no common divisor greater than 1 even though each individual modulus may be divisible by other than one and the number itself. Using this restricted class any integer N can be uniquely coded in a residue number system as a sequence of residue digits [r.sub.1, r.sub.2, .. . , r.sub.L ]where the moduli are relatively prime.
The range of the system is from 0 tW-1 where W is the product of the moduli. If negative numbers are to be represented, the range is -W/2 to (W/2)-1 when W is even.
In moduli form the number N is sometimes represented as N (P.sub.1, P.sub.2, P.sub.3, . . . , P.sub.L) where P.sub.1, P.sub.2, P.sub.3, ..., P.sub.L are the co-prime moduli. Where, for example, N is an operand equal to 18 and the moduli set is 7, 15, 17 then the residues are 4, 3 and 1 and this set of residue values [4, 3, 1] uniquely represents the operand value 18. The range W-1 of this moduli system is (7.15.17)-1=1784.
These residues are dependent only upon their corresponding modulus and not upon each other. In this way each residue can be operated on independently of the others. Further, there are no burrows or carries and the word lengths of these residues are much shorter than the decimal or digital word lengths, thereby allowing faster operations with less hardware. The limited number of solutions within each channel permits their storage in ROMS for fast access. The signal processor operates on each of the residue values independently using the periodic modulo arithmetic. Although some RNS operations are relatively cumbersome, those involving multiplication and addition can be relatively fast and are therefore attractive in digital filter designs such as FIR types which are implemented with multiplication and addition.
After the signal processor has finished executing all of the periodic residue operations on each of the individual inputted residue values, a decoding method must then be implemented to convert the processed residue values into the true external representation of the output. This is often a cumbersome process involving significant computational overhead.
Decoding residue numbers is frequently based upon an implementation of the chinese remainder theorem (CRT). This theorem takes each individual residue and multiples it by a distinct coefficient corresponding to the individual modulus. These products are then all summed together. The summation is then reduced using modulo reduction. The chinese remainder theorem can be expressed as: ##EQU1## where N.sub.out is the true external representation of the processed value, C.sub.i is the individual CRT coefficient and M is the product of all the moduli, P.sub.i. The CRT coefficient, C.sub.i, can be obtained through the relationship, EQU C.sub.i =i(M/P.sub.i)=1 Mod(P.sub.i) where O&lt;b.sub.i &lt;P.sub.i. ( 4)
By finding all of the CRT coefficients and utilizing them in the CRT summation, N.sub.out may be obtained. This final output is the true external representation of the processed signal.
To implement the chinese remainder theorem in digital processing, a separate equivalent form of the CRT is used such that ##EQU2## where s is the number of moduli to be decoded and k is the CRT value address.
This form is then reduced using Horner's rule to yield a recursive expression of the form EQU N.sub.out =(f(s-1)+2(f) (s-2)+. . . 2(f(1)+2(f(0)) . . . Mod M. (6)
This is the final function that represents the implemented algorithm.
In order to increase system speed the function values, (f(k) can each be multiplied prior to decoding and stored in memory. These values can be accessed during decoding because they are uniquely determined by the address, k.
While residue processor decoders have been proposed for various signal processing applications, they are incapable of meeting the needs of some systems having stringent throughput, accuracy and range requirements.
It is accordingly an object of the invention to provide RNS signal decoding techniques which are capable of real time operation in applications requiring high accuracy and speed.
Another object is to provide such techniques which are capable of wide dynamic range utilizing a relatively small number of channels.
A further object of the invention is the provision of filter techniques which are flexible with respect to the number of moduli utilized and their values.
A still further object is to provide filtering techniques which are hardware transparent. Various families of components may be used in implementing the functional elements of the circuit.